package com.ma;

public class sort {
    /**
     * 归并排序
     * O(n)
     * @param arr
     * @param L
     * @param M
     * @param R
     */
    public static void marge(int[] arr,int L,int M,int R){
        int[] help=new int[R-L+1];
        int i=0
                ,p1=L//左组起始位置
                ,p2=M+1//右组起始位置
        ;
        //在不出界的前提下将小的扔给help
        while (p1<=M&&p2<=R){
            help[i++]=arr[p1]<=arr[p2]?arr[p1++]:arr[p2++];
        }
        //一旦有出界执行下面，将没出界剩下的赋给help
        while (p1<=M){
            help[i++]=arr[p1++];
        }
        while (p2<=R){
            help[i++]=arr[p2++];
        }
        for(i=0;i<help.length;i++){
            arr[L+i]=help[i];
        }
    }


    /**
     * 快速排序v3.0
     * O(N*logN)
     * 详细看荷兰国旗问题的解答 problem.dutchFlag
     * 优化前
     *      v1.0:分<=区和>区 O(N*2)
     *      v2.0:分三区但没做随机交换 按最差情况:O(N^2)
     * @param arr
     * @param L
     * @param R
     */
    public static void quickSort(int[] arr,int L,int R){
        if(L>=R){
            return;
        }
        swap(arr, L+(int) (Math.random()*(R-L+1)),R);//随机位置与最后一个交换以避免最差情况(即12345678这样的情况)
        int[] qS = qSortUnit(arr, L, R);
        quickSort(arr,L,qS[0]-1);
        quickSort(arr,qS[1]+1,R);
    }
    public static int[] qSortUnit(int[] arr,int L,int R){
        if(L>R){
            return new int[]{-1,-1};
        }
        if(L==R){
            return new int[]{L,R};
        }


        int less=L-1;
        int more=R;
        int i=L;
        while (i<more){
            if(arr[i]==arr[R]){
                i++;
            }else if(arr[i]<arr[R]){
                swap(arr,i++,++less);
            }else {
                swap(arr,i,--more);
            }
        }
        swap(arr,more,R);
        return new int[]{less+1,more};
    }

    public static void swap(int[] arr,int i,int j){
        if(i==j){
            return;
        }
        arr[i]=arr[i]^arr[j];
        arr[j]=arr[i]^arr[j];
        arr[i]=arr[i]^arr[j];
    }

}
